這篇文章會用 TDD 手刻 myReduce、myReduceOrNull、myReduceIndexed，理解 reduce 和 fold 的差異

Kotlin ↔ C# 對照表

reduce vs fold

上一篇的 fold 需要一個初始值。reduce 不需要，它拿集合的第一個元素當初始值，從第二個元素開始折疊

fold(0):    0 → +1 → +2 → +3 = 6
reduce:     1 → +2 → +3 = 6

結果一樣，但 reduce 少了一個參數。代價是兩個限制

第一，reduce 的累加器可以是元素型別或其父型別，但不能是無關型別。fold 可以把 List<Employee> 折成 Int；reduce 的第一個累加值來自 Employee，因此做不到這種轉換

第二，空集合會出事。fold 遇到空集合直接回傳初始值，reduce 沒有初始值，只能拋例外。reduceOrNull 是安全版，空集合回傳 null

TDD 實作 myReduce

Red：先寫測試

@Test
fun `reduce sum of numbers`() {
    val numbers = listOf(1, 2, 3, 4, 5)
    val result = numbers.myReduce { acc, num -> acc + num }
    assertEquals(15, result)
}

@Test
fun `reduce find max`() {
    val numbers = listOf(3, 7, 2, 9, 4)
    val result = numbers.myReduce { acc, num -> if (num > acc) num else acc }
    assertEquals(9, result)
}

@Test
fun `reduce single element returns that element`() {
    val single = listOf(42)
    val result = single.myReduce { acc, num -> acc + num }
    assertEquals(42, result)
}

@Test
fun `reduce empty list throws exception`() {
    val empty = emptyList<Int>()
    assertThrows<UnsupportedOperationException> {
        empty.myReduce { acc, num -> acc + num }
    }
}

第二個測試用 reduce 找最大值。第一個元素當初始的「目前最大」，後續每個元素跟它比，大的留下

單一元素的測試驗證 Lambda 根本不會被呼叫，直接回傳那個唯一的元素

空集合拋 UnsupportedOperationException，這跟 stdlib 的行為一致

employees 也能用 reduce，但要注意它適合「最後仍然回傳某個 Employee」的情境，例如找出薪水最高的人

val highestPaid = employees.myReduce { acc, emp ->
    if (emp.salary > acc.salary) emp else acc
}

highestPaid.name // Grace

如果目標是薪水總和，回傳型別會從 Employee 變成 Int，這時就該用上一篇的 fold

Green：最小實作

inline fun <S, T : S> Iterable<T>.myReduce(operation: (acc: S, T) -> S): S {
    val iterator = this.iterator()
    if (!iterator.hasNext()) {
        throw UnsupportedOperationException("Empty collection can't be reduced.")
    }
    var accumulator: S = iterator.next()
    while (iterator.hasNext()) {
        accumulator = operation(accumulator, iterator.next())
    }
    return accumulator
}

不能用 for 迴圈，因為要跳過第一個元素。手動拿 iterator，先 next() 一次取出第一個元素當累加器，剩下的用 while 跑

泛型簽名 <S, T : S> 要拆開來看。T : S 代表 T 是 S 的子型別。Lambda 的簽名是 (acc: S, T) -> S，回傳型別是 S 而不是 T

為什麼？想像你有 List<Int>，用 reduce 算出結果。Int 的加法回傳的是 Int，但如果 Lambda 回傳的是 Number(Int 的父型別)呢？S 就是 Number，T 就是 Int。T : S 確保 Int 是 Number 的子型別，所以第一個 Int 元素可以安全地賦值給 S 型別的累加器

老實說，大多數情況下 S 和 T 是同一個型別。這個泛型設計是為了型別系統的完整性

具體一點看

val ints: List<Int> = listOf(1, 2, 3)

// 一般情況：Lambda 回傳 Int → S = T = Int
val sum: Int = ints.reduce { acc, n -> acc + n }

罕見情境：把 List<Int> reduce 成 Number(Int 的父型別)，這時 S = Number、T = Int，T : S 約束保證型別安全

數學直覺：reduce 的累加器型別只要「能容納」元素型別就行。元素是 Int，累加器可以是 Int、Number、Any，任何 Int 的父型別都行。T : S 把這個「向上相容」的關係寫進泛型約束裡

對照表裡 reduce 對應的是 C# 的無 seed 版 Aggregate，也就是 Aggregate<TSource>(Func<TSource, TSource, TSource>)。這個多載只有一個泛型參數 TSource，累加器和元素被強制成同一個型別，比 Kotlin 的 <S, T : S> 更死。Kotlin 至少允許 S 是 T 的父型別，C# 無 seed 版連這個彈性都沒有。如果想讓累加器跟元素不同型別，C# 得改用有 seed 的 Aggregate<TSource, TAccumulate> 多載，但那是 fold 的對應版本，不是 reduce

Refactor：往 stdlib 的寫法靠近

沒有要動的地方。手動拿 iterator、先 next() 一次再 while 的結構就是 stdlib 的寫法，後面的原始碼比較會證明這件事

TDD 實作 myReduceOrNull

Red：先寫測試

@Test
fun `reduceOrNull empty list returns null`() {
    val empty = emptyList<Int>()
    val result = empty.myReduceOrNull { acc, num -> acc + num }
    assertNull(result)
}

@Test
fun `reduceOrNull non-empty list reduces normally`() {
    val numbers = listOf(1, 2, 3, 4)
    val result = numbers.myReduceOrNull { acc, num -> acc + num }
    assertEquals(10, result)
}

非空集合沿用 myReduce 的行為；差別只在空集合不拋例外，改回傳 null

Green：最小實作

inline fun <S, T : S> Iterable<T>.myReduceOrNull(operation: (acc: S, T) -> S): S? {
    val iterator = this.iterator()
    if (!iterator.hasNext()) {
        return null
    }
    var accumulator: S = iterator.next()
    while (iterator.hasNext()) {
        accumulator = operation(accumulator, iterator.next())
    }
    return accumulator
}

跟 myReduce 只差兩個地方：回傳型別從 S 變成 S?，空集合從拋例外變成 return null。這個模式跟 day 06 的 first vs firstOrNull 完全一樣

Refactor：往 stdlib 的寫法靠近

這個版本保留與 myReduce 相同的結構，只改空集合的處理方式

TDD 實作 myReduceIndexed

Red：先寫測試

@Test
fun `reduceIndexed with index weighting`() {
    val numbers = listOf(10, 20, 30)
    val result = numbers.myReduceIndexed { index, acc, num -> acc + num * index }
    // 第一個元素(index 0)直接當初始值: 10
    // index 1: 10 + 20*1 = 30
    // index 2: 30 + 30*2 = 90
    assertEquals(90, result)
}

@Test
fun `reduceIndexed single element returns that element`() {
    val single = listOf(42)
    val result = single.myReduceIndexed { _, acc, num -> acc + num }
    assertEquals(42, result)
}

@Test
fun `reduceIndexed empty list throws exception`() {
    val empty = emptyList<Int>()
    assertThrows<UnsupportedOperationException> {
        empty.myReduceIndexed { _, acc, num -> acc + num }
    }
}

跟 myReduce 一樣，空集合沒有第一個元素可拿來當初始值，只能拋 UnsupportedOperationException；單一元素則 Lambda 不會被呼叫，直接回傳

Green：最小實作

inline fun <S, T : S> Iterable<T>.myReduceIndexed(operation: (index: Int, acc: S, T) -> S): S {
    val iterator = this.iterator()
    if (!iterator.hasNext()) {
        throw UnsupportedOperationException("Empty collection can't be reduced.")
    }
    var accumulator: S = iterator.next()
    var index = 1
    while (iterator.hasNext()) {
        accumulator = operation(index, accumulator, iterator.next())
        index++
    }
    return accumulator
}

注意 var index = 1，不是 0。因為第一個元素(index 0)已經被拿去當初始值了，Lambda 從 index 1 開始執行

Refactor：往 stdlib 的寫法靠近

var index = 1 起跳的寫法跟 stdlib 一致

與 stdlib 原始碼比較

原始碼位置：kotlin.collections 的 _Collections.kt

public inline fun <S, T : S> Iterable<T>.reduce(operation: (acc: S, T) -> S): S {
    val iterator = this.iterator()
    if (!iterator.hasNext()) throw UnsupportedOperationException("Empty collection can't be reduced.")
    var accumulator: S = iterator.next()
    while (iterator.hasNext()) {
        accumulator = operation(accumulator, iterator.next())
    }
    return accumulator
}

兩份實作的控制流程與例外訊息都相同

何時用 fold，何時用 reduce？

可以從以下條件判斷

用 fold：累加器型別與元素無關、集合可能為空、需要自訂初始值

用 reduce：累加器是元素型別或其父型別，而且確定集合不是空的

不確定的話就用 fold，比較安全。reduce 只是語法上少一個參數，省不了多少事

小結

reduce 是 fold 的專用版，用第一個元素當初始值。好處是少一個參數；限制是空集合會拋例外，而且累加器只能是元素型別或其父型別

泛型簽名 <S, T : S> 第一次在這個系列出現。雖然實務上 S 和 T 幾乎都是同一個型別，但從型別系統的角度看，這個設計讓 reduce 的行為更精確

fold 和 reduce 都到齊了，下一篇要拿它們去還一筆債。day 14 介紹 groupBy 時提到 groupingBy 回傳的 Grouping 介面，當時因為還沒講折疊而跳過實作。day 19 會把那個介面連同 aggregate、fold、reduce、eachCount 四個操作一次實作完

參考資料

• Kotlin API：reduce
• Kotlin API：reduceOrNull
• Kotlin API：reduceIndexed
• Kotlin API：reduceIndexedOrNull
• Kotlin API：reduceRight
• Kotlin API：scan
• Kotlin API：fold
• Kotlin API：maxByOrNull
• Kotlin API：iterator
• Kotlin API：Iterator
• Kotlin API：Iterable
• Kotlin API：UnsupportedOperationException
• Kotlin API：aggregate
• Kotlin API：eachCount
• Kotlin stdlib 原始碼：_Collections.kt
• Java API：Stream.reduce
• Java API：Optional
• .NET API：Enumerable.Aggregate
• .NET API：Enumerable.MaxBy
• C# 官方文件：標準查詢運算子

同步刊登於 Blog

圖片來源：AI 產生